/*  Copyright 2010 Daniel Brasil Magnani
 *  Created on: Dec 20, 2010
 *      Author: daniel
 */

#include "solution.h"

using std::vector;
using std::swap;
using std::sort;

bool Compare(const int *a, const int *b) {
  return (a[1] < b[1]);
}

void Solution::CalculateSolution() {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  int counter;
  for (int i = 0; i < constraint_size_; i++) {
    max_profit_[i][1] = 0;
    for (int j = 0; j < solution_size_+yesterday_size_; j++) {
      counter = 0;
      for (int l = 0; l < constraint_list[i].p; l++) {
        if ( j >= yesterday_size_ )
          counter += solution_[j-l].constraints[i];
      }
      if ( counter > constraint_list[i].n )
        max_profit_[i][1] += counter - constraint_list[i].n;
    }
  }
  sort(max_profit_.begin(), max_profit_.end(), Compare);
}

void Solution::CreateStructures(int algorithm) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  for (int i = 0; i < constraint_size_; i++) {
    for (int j = 0; j < solution_size_+yesterday_size_; j++) {
      M1_[i][j] = 0;
      for (int l = 0; l < constraint_list[i].p; l++) {
        if ( j < solution_size_ )
          M1_[i][j] += solution_[j+l].constraints[i];
      }
    }
  }
  if ( algorithm == 1 )
    UpdateM_();
}

void Solution::UpdateStructures(int u, int v, int algorithm) {
  UpdateM1(u);
  UpdateM1(v);
  if ( algorithm == 1 )
    UpdateM_();
}

void Solution::UpdateM1(int u) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  for (int i = 0; i < constraint_size_; i++) {
    for (int j = u-constraint_list[i].p; j <= u; j++) {
      if ( j < 0 )
        j = 0;
      M1_[i][j] = 0;
      for (int l = 0; l < constraint_list[i].p; l++) {
        if ( j < solution_size_ )
          M1_[i][j] += solution_[j+l].constraints[i];
      }
    }
  }
}

void Solution::UpdateM_() {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  for (int i = 0; i < constraint_size_; i++) {
    for (int j = 0; j < solution_size_+yesterday_size_; j++) {
      if ( j == 0 ) {
        if ( M1_[i][j] > constraint_list[i].n ) {
          M2_[i][j] = 1;
          M3_[i][j] = 1;
        } else if ( M1_[i][j] == constraint_list[i].n ) {
          M2_[i][j] = 0;
          M3_[i][j] = 1;
        } else {
          M2_[i][j] = 0;
          M3_[i][j] = 0;
        }
      } else if ( M1_[i][j] > constraint_list[i].n ) {
        M2_[i][j] = M2_[i][j-1]+1;
        M3_[i][j] = M3_[i][j-1]+1;
      } else if ( M1_[i][j] == constraint_list[i].n ) {
        M2_[i][j] = M2_[i][j-1];
        M3_[i][j] = M3_[i][j-1]+1;
      } else {
        M2_[i][j] = M2_[i][j-1];
        M3_[i][j] = M3_[i][j-1];
      }
    }
  }
}

int Solution::SwapVariation(int i, int j, int k, int algorithm) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  int variation = 0;
  int decrease_min_bound;
  int decrease_max_bound;
  int increase_min_bound;
  int increase_max_bound;
  if ( i > j ) {
    increase_min_bound = std::max(j+1, i-constraint_list[k].p+1);
    increase_max_bound = i;
    decrease_min_bound = j-constraint_list[k].p+1;
    decrease_max_bound = std::min(i-constraint_list[k].p, j);
  } else {
    decrease_min_bound = std::max(i+1, j-constraint_list[k].p+1);
    decrease_max_bound = j;
    increase_min_bound = i-constraint_list[k].p+1;
    increase_max_bound = std::min(j-constraint_list[k].p, i);
  }

  if ( algorithm == 0 ) {
    for (int l = decrease_min_bound;l <= decrease_max_bound;l++) {
      if ( M1_[k][l] > constraint_list[k].n ) {
        variation--;
      }
    }
    for (int l = increase_min_bound;l <= increase_max_bound;l++) {
      if ( M1_[k][l] >= constraint_list[k].n ) {
        variation++;
      }
    }
  } else {
    if ( i-constraint_list[k].p > 0 )
      variation += M3_[k][increase_max_bound] - M3_[k][increase_min_bound-1];
    else
      variation += M3_[k][increase_max_bound];

    if ( j-constraint_list[k].p > 0 )
      variation -= M2_[k][decrease_max_bound] - M2_[k][decrease_min_bound-1];
    else
      variation -= M2_[k][decrease_max_bound];
  }

  return variation;
}

int Solution::SwapCost(int i, int j, int k, int algorithm) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  int variation;
  variation = 0;
  if ( solution_[i].constraints[k] != solution_[j].constraints[k] ) {
    if ( solution_[i].constraints[k] < solution_[j].constraints[k] ) {
      variation = SwapVariation(i, j, k, algorithm);
    } else {
      variation = SwapVariation(j, i, k, algorithm);
    }
  }
  return variation;
}

void Solution::Swap(int i, int j) {
  swap(solution_[i], solution_[j]);
}

std::vector<Car> Solution::get_solution() {
  return solution_;
}

Solution::Solution(const std::vector<Car> &solution) {
  vector<Constraint> constraint_list;
  vector<Car> yesterday_cars;
  vector<Car> today_cars;
  constraint_list = Instance::get_instance().get_constraint_list();
  yesterday_cars = Instance::get_instance().get_yesterday_cars();
  today_cars = Instance::get_instance().get_today_cars();

  solution_.reserve(solution.size()+yesterday_cars.size());
  copy(solution.begin(), solution.end(), back_inserter(solution_));
  constraint_size_ = constraint_list.size();
  solution_size_ = solution_.size();
  yesterday_size_ = yesterday_cars.size();
  map_ = new int[solution_size_+yesterday_size_];
  max_profit_.resize(constraint_size_);

  M1_.resize(constraint_size_);
  M2_.resize(constraint_size_);
  M3_.resize(constraint_size_);

  // Dummy cars
  Car temp_car;
  temp_car.identifier = 0;
  temp_car.constraints = new int[constraint_size_];
  for (int i = 0; i < constraint_size_; i++) {
    temp_car.constraints[i] = 0;
    M1_[i].resize(solution_size_+yesterday_size_);
    M2_[i].resize(solution_size_+yesterday_size_);
    M3_[i].resize(solution_size_+yesterday_size_);
    max_profit_[i] = new int[2];
    max_profit_[i][0] = i;
    max_profit_[i][1] = 0;
  }
  for (int i = 0; i < yesterday_cars.size() ; i++) {
    solution_.push_back(temp_car);
  }
}

void Solution::GetCars(int *cars) {
  vector<Constraint> constraint_list;
  constraint_list = Instance::get_instance().get_constraint_list();

  int i, j;
  i = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
  j = i;
  while ( j == i )
    j = rand()%(solution_size_ - yesterday_size_) + yesterday_size_;
  cars[0] = i;
  cars[1] = j;
}

int Solution::VFLS(float time_limit, int algorithm, int target) {
  int total_variation;
  int* cars = new int[2];
  int remaining_profit;
  int visits = 0;
  int changes = 0;

  CreateStructures(algorithm);
  CalculateSolution();
  remaining_profit = 0;
  for ( int k = 0; k < constraint_size_; k++ ) {
    remaining_profit += max_profit_[k][1];
  }
  Chronometer chronometer;
  chronometer.Time();
  while ( chronometer.Value() < time_limit ) {
    GetCars(cars);
    int i = cars[0];
    int j = cars[1];

    total_variation = 0;
    if ( remaining_profit <= target ) {
      printf("%d %lf %d %d\n", remaining_profit, chronometer.dValue(),
             visits, changes);
      return true;
    }
    for ( int k = 0; k < constraint_size_; k++ ) {
      total_variation += SwapCost(i, j,
                         max_profit_[k][0], algorithm);
      if ( total_variation > remaining_profit )
        break;
    }
    if ( total_variation <= 0 ) {
      Swap(i, j);
      UpdateStructures(i, j, algorithm);
      changes++;
      remaining_profit += total_variation;
    }
    visits++;
  }
  printf("%d %lf %d %d\n", remaining_profit, time_limit, visits, changes);
  return true;
}

int Solution::LocalSearch(int algorithm, int improving) {
  int change = 1;
  int total_variation, max_variation, best_variation;
  int random = 65;
  int visits = 0;
  int changes = 0;
  int remaining_profit;
  int u, v;

  CreateStructures(algorithm);
  CalculateSolution();
  remaining_profit = 0;
  for ( int k = 0; k < constraint_size_; k++ ) {
    remaining_profit += max_profit_[k][1];
  }

  Chronometer chronometer;
  chronometer.Time();
  while ( change != 0 ) {
    change = 0;
    best_variation = INT_MAX;
    for ( int i = yesterday_size_; i < solution_size_; i++ ) {
      max_variation = INT_MAX;
      for ( int j = i+1; j < solution_size_; j++ ) {
        total_variation = 0;
        for ( int k = 0; k < constraint_size_; k++ ) {
          total_variation += SwapCost(i, j, k, algorithm);
        }
        if ( total_variation < max_variation ) {
          if ( improving < 2 ) {
            u = i;
            v = j;
            max_variation = total_variation;
            if ( improving == 0 && total_variation < 0 )
              break;
          } else if ( total_variation < best_variation ) {
            u = i;
            v = j;
            best_variation = total_variation;
          }
        }
        visits++;
      }
      if ( improving < 2 && max_variation < 0 ) {
        change = 1;
        Swap(u, v);
        UpdateStructures(u, v, algorithm);
        remaining_profit += max_variation;
        changes++;
      }
    }
    if ( improving == 2 && best_variation < 0 ) {
      change = 1;
      Swap(u, v);
      UpdateStructures(u, v, algorithm);
      remaining_profit += best_variation;
      changes++;
    }
  }
  printf("%d %lf %d %d\n", remaining_profit, chronometer.dValue(),
         visits, changes);
  return true;
}
